`/*
	大数相乘分治思想：
	将两个n位数分为两截
	X = A * 10^n/2 + B
	Y = C * 10^n/2 + D

	XY = (A * 10^n/2 + B) * (C * 10^n/2 + D)
	   = AC * 10^n + (AD + BC)*10^n/2 + BD

	T(n) = O(1)   ,n = 1
	      = 4T(n/2) + O(n)  ,n > 1
	递归求和后 O(n^2)

	改进
	XY = AC * 10^n + ( (A - B)(D - C) + AC + BD)*10^n/2 + BD 
	
	T(n) = 3T(n/2) + O(n)
*/

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define SIGN(A)((A > 0)?1:-1)

long longMultiply(long X, long Y, int n)
{
	long sign = SIGN(X)*SIGN(Y);//正负号
	long x = abs(X);
	long y = abs(Y);

	if (x == 0 || y == 0)
		return 0;
	else if (n == 1)
		return sign*x*y;
	else
	{
		long A = (long) x / pow(10, n/2);
		long B = X - ;

		long C = (long) y / pow(10, n/2);
		long D = (long)(y % (int)pow(10, n/2));

		long AC = longMultiply(A,C,n/2);
		long BD = longMultiply(B,D,n/2);

		long ABCD = longMultiply((A - B), (D - C), n/2) + AC + BD;

		return (long)(sign * (AC * pow(10, n) +ABCD * pow(10, n/2) + BD));
	}
}

int main(void)
{
	long a = 1234;
	long b = 5678;
	long c = longMultiply(a,b,4);

	printf("%ld\n",c);
}